//
// Description: 5665. 从相邻元素对还原数组
// Created by Loading on 2021/1/31.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> restoreArray(vector<vector<int>> &adjacentPairs) {
    unordered_map<int, int> m;//用于判断元素出现次数，寻找开头和结尾
    unordered_map<int, deque<int>> statistics;//统计每个元素及其相邻点的 hash表
    vector<int> res;

    //数组的开始和结尾
    int start = INT_MIN, end = INT_MIN;

    for (auto &v : adjacentPairs) {
        if (statistics[v[0]].empty()) {
            statistics[v[0]] = {v[1]};
        } else {
            statistics[v[0]].emplace_back(v[1]);
        }

        if (statistics[v[1]].empty()) {
            statistics[v[1]] = {v[0]};
        } else {
            statistics[v[1]].emplace_back(v[0]);
        }
        m[v[0]]++;
        m[v[1]]++;
    }
    for (auto &it : m) {//寻找开头和结尾
        if (it.second == 1) {
            if (start == INT_MIN) {
                start = it.first;
            } else {
                end = it.first;
                break;
            }
        }
    }

    while (!statistics.empty()) {//hash表空。跳出
        if (statistics[start].size() == 1) {
            //取得相邻节点，start与temp相邻，相反，temp也与start相邻
            int temp = statistics[start][0];
            //start的相邻节点temp已使用，从hash表中删除
            statistics.erase(start);
            //在temp的相邻节点中，删掉start
            if (statistics[temp][0] == start) {
                statistics[temp].pop_front();
            } else {
                statistics[temp].pop_back();
            }
            //加入vector
            res.emplace_back(start);
            //更新start
            start = temp;
        } else {//仅剩一个结尾
            break;
        }
    }
    res.emplace_back(end);

    return res;
}

int main() {
    vector<vector<int>> v = {{2, 1},
                             {3, 4},
                             {3, 2}};
    vector<int> res = restoreArray(v);
    for (auto x : res) {
        cout << x << " ";
    }
}